package com.fireway;

import java.util.NoSuchElementException;

/**
 * 链表实现的栈
 * 2018年 05月 03日 星期四
 *
 * @author fireway
 */
public class Stack {
    private SingleLinkedList<Long> mList;

    public Stack() {
        mList = new SingleLinkedList<Long>();
    }

    /**
     * 入栈
     * put item on top of stack
     */
    public void push(long item) {
        mList.addFirst(item);
    }

    /**
     * 出栈
     * take item from top of stack
     */
    public long pop() {
        return mList.removeFirst();
    }

    /**
     * 查看
     * peek at top of stack
     */
    public long peek() {
        return mList.getFirst();
    }

    /**
     * 是否栈空。
     * true if stack is empty
     */
    public boolean empty() {
        return mList.empty();
    }

    @Override
    public String toString() {
        return "Stack " + mList.toString();
    }

    /* package */static class SingleLinkedList<E> {
        private Entry<E> mHeader;  // 表头

        private int mSize = 0;

        public SingleLinkedList() {
            mHeader = null;
        }

        /**
         * Inserts the specified element at the beginning of this list.
         *
         * @param e the element to add
         */
        public void addFirst(E e) {
            Entry<E> newEntry = new Entry<E>(e, mHeader);    // newEntry --> old Entry
            mHeader = newEntry;                              // mHeader --> newEntry
            mSize++;
        }

        /**
         * Removes and returns the first element from this list.
         *
         * @return the first element from this list
         */
        public E removeFirst() {
            if (empty()) {
                throw new NoSuchElementException();
            } else {
                Entry<E> tmp = mHeader;
                E result = tmp.mElement;
                mHeader = tmp.mNext;
                mSize--;
                return result;

            }
        }

        /**
         * Returns the first element in this list.
         *
         * @return the first element in this list
         * @throws NoSuchElementException if this list is empty
         */
        public E getFirst() {
            if (empty()) {
                throw new NoSuchElementException();
            }

            return mHeader.mElement;
        }

        public boolean empty() {
            // 当mHeader的值为null，就表明链表中没有数据项。
            // 如果有，mHeader应该存有对第一个链接点
            // 的引用值。
            return null == mHeader;
        }

        /**
         * Returns the index of the first occurrence of the specified element
         * in this list, or -1 if this list does not contain the element.
         *
         */
        public int indexOf(Object o) {
            int index = 0;
            for (Entry<E> e = mHeader; e != null ; e = e.mNext) {
                if (isEqual(o, e.mElement)) {
                    return index;
                }
                index++;
            }

            return -1;
        }

        /**
         * Returns the element at the specified position in this list.
         * @param index index of the element to return
         * @return the element at the specified position in this list
         */
        public E get(int index) {
            if (index < 0 || index >= mSize) {
                throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + mSize);
            }

            Entry<E> e = mHeader;
            for (int i = 0; i < index; i++) {
                e = e.mNext;
            }

            return e.mElement;
        }

        public boolean remove(Object o) {
            Entry<E> current = mHeader;
            Entry<E> previous = null;

            while (current != null) {
                if (isEqual(o, current.mElement)) {
                    break;
                }
                previous = current;
                current = current.mNext;
            }

            if (null == previous) {
                mHeader = mHeader.mNext;
            } else if (null == current) {
                return false;
            } else {
                previous.mNext = current.mNext;
            }

            mSize--;
            return true;
        }

        private boolean isEqual(Object o, E element) {
            if (null == o) {
                return element == null;
            } else {
                return o.equals(element);
            }
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer();

            sb.append("[");
            for (int i = 0; i < mSize; i++) {
                E e = get(i);
                sb.append(e);
                if (i != mSize - 1) {
                    sb.append(", ");
                }
            }
            sb.append("]");

            return sb.toString();
        }

        private static class Entry<E> {
            E mElement;
            Entry<E> mNext;

            public Entry(E element, Entry<E> next) {
                mElement = element;
                mNext = next;
            }
        }
    }
}
